package org.xx.armory.commons;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;
import java.util.function.Consumer;

import static org.xx.armory.commons.Validators.notNull;

/**
 * 树形结构相关的工具类。
 */
public final class TreeUtils {
    private TreeUtils() {
        throw new UnsupportedOperationException();
    }

    /**
     * 执行广度优先遍历。
     *
     * @param <E>
     *         树形结构关联的类型。
     * @param root
     *         需遍历的根节点。
     * @param c
     *         遍历中的节点处理方法。
     * @throws IllegalArgumentException
     *         如果参数{@code c}是{@code null}。
     */
    public static <E> void forEachBreadth(
            Tree.Node<E> root,
            Consumer<Tree.Node<E>> c
    ) {
        notNull(root, "root");
        notNull(c, "c");

        final Queue<Tree.Node<E>> q = new ArrayDeque<>();

        q.add(root);

        while (!q.isEmpty()) {
            final Tree.Node<E> node = q.remove();
            q.addAll(node.children());
            c.accept(node);
        }
    }

    /**
     * 执行广度优先遍历。
     *
     * @param <E>
     *         树形结构关联的类型。
     * @param tree
     *         需遍历的树形结构。
     * @param c
     *         遍历中的节点处理方法。
     * @throws IllegalArgumentException
     *         如果参数{@code c}是{@code null}。
     */
    public static <E> void forEachBreadth(
            Tree<E> tree,
            Consumer<Tree.Node<E>> c
    ) {
        notNull(tree, "tree");
        notNull(c, "c");

        final Queue<Tree.Node<E>> q = new ArrayDeque<>(tree.roots());

        while (!q.isEmpty()) {
            final Tree.Node<E> node = q.remove();
            q.addAll(node.children());
            c.accept(node);
        }
    }

    /**
     * 执行深度优先遍历（先序）。
     *
     * @param <E>
     *         树形结构关联的类型。
     * @param root
     *         需遍历的根节点。
     * @param c
     *         遍历中的节点处理方法。
     * @throws IllegalArgumentException
     *         如果参数{@code c}是{@code null}。
     */
    public static <E> void forEachDepth(
            Tree.Node<E> root,
            Consumer<Tree.Node<E>> c
    ) {
        notNull(root, "root");
        notNull(c, "c");

        final Deque<Tree.Node<E>> q = new ArrayDeque<>();

        c.accept(root);

        // 反向压栈
        List<Tree.Node<E>> tempList = new ArrayList<>(root.children());
        for (int i = tempList.size() - 1; i >= 0; --i) {
            q.add(tempList.get(i));
        }

        while (!q.isEmpty()) {
            final Tree.Node<E> node = q.removeLast();
            c.accept(node);

            // 反向压栈
            tempList = new ArrayList<>(node.children());
            for (int i = tempList.size() - 1; i >= 0; --i) {
                q.add(tempList.get(i));
            }
        }
    }

    /**
     * 执行深度优先遍历（先序）。
     *
     * @param <E>
     *         树形结构关联的类型。
     * @param tree
     *         需遍历的树形结构。
     * @param c
     *         遍历中的节点处理方法。
     * @throws IllegalArgumentException
     *         如果参数{@code c}是{@code null}。
     */
    public static <E> void forEachDepth(
            Tree<E> tree,
            Consumer<Tree.Node<E>> c
    ) {
        notNull(tree, "tree");
        notNull(c, "c");

        final Deque<Tree.Node<E>> q = new ArrayDeque<>();

        // 反向压栈
        List<Tree.Node<E>> tempList = new ArrayList<>(tree.roots());
        for (int i = tempList.size() - 1; i >= 0; --i) {
            q.add(tempList.get(i));
        }

        while (!q.isEmpty()) {
            final Tree.Node<E> node = q.removeLast();
            c.accept(node);

            // 反向压栈
            tempList = new ArrayList<>(node.children());
            for (int i = tempList.size() - 1; i >= 0; --i) {
                q.add(tempList.get(i));
            }
        }
    }
}
